import numpy as np
from scipy.optimize import minimize
def svm(X, y):
    '''
    SVM Support vector machine.

    INPUT:  X: training sample features, P-by-N matrix.
            y: training sample labels, 1-by-N row vector.

    OUTPUT: w: learned perceptron parameters, (P+1)-by-1 column vector.
            num: number of support vectors

    '''
    P, N = X.shape
    w = np.zeros((P + 1, 1))
    num = 0

    # YOUR CODE HERE
    # Please implement SVM with scipy.optimize. You should be able to implement
    # it within 20 lines of code. The optimization should converge wtih any method
    # that support constrain.
    #TODO
    # begin answer
    # end answer
    X1 = np.vstack((np.ones((1, N)), X))
    fun = lambda w_vec: 0.5 * np.dot(w_vec, w_vec)
    cons = [
        {
            'type': 'ineq',
            'fun': lambda w_vec, Xi=X1[:, i], yi=y[0, i]: yi * (w_vec.dot(Xi)) - 1
        }
        for i in range(N)
    ]
    res = minimize(fun, np.zeros(P + 1), constraints=cons, method='SLSQP')
    w = res.x.reshape(-1, 1)
    margins = y * (w.T.dot(X1))
    num = int(np.sum(np.abs(margins - 1) < 1e-6))
    return w, num

